package com.example.demo.leetcode.zijie;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 *
 */
public class String_大数相乘 {

    public static String multipy(String a,String b){

        //遍历b，拆分循环，取出每个字符的 值 和倍数，比如 99 拆成 9 * 10 和 9
        StringBuffer bufferB = new StringBuffer(b);
        StringBuffer bufferA = new StringBuffer(a);
        char [] bArr =   bufferB.reverse().toString().toCharArray();
        char [] aArr =   bufferA.reverse().toString().toCharArray();
        List<String> addList = new ArrayList<String>();
        for(int i=0;i<bArr.length;i++ ){
            // i 表示位数 0表示个位，1表示十位
            char tempb = bArr[i];
            for(int j=0;j<aArr.length;j++){
                //遍历a,拆分循环，取出每个字符的值 和 倍数
                char tempa = aArr[j];
                //j 表示位数
                int b1 = Integer.parseInt(tempb+"");
                int a1 = Integer.parseInt(tempa+"");
                Integer tempEnd = a1 * b1 ;
                StringBuffer tempStr = new StringBuffer(tempEnd+"");
                for(int k=0;k<i+j;k++){
                    tempStr.append("0");
                }
                addList.add(tempStr.toString());
            }
        }
        //a,b的 值相乘，倍数长度累加，结果存入list中，list中每个数进行 大数累加
        String res = addList.get(0);
        for(int i = 1; i<addList.size();i++){
            res = add(res,addList.get(i));
        }
        return res;
    }

    // 大数累加
    public static String add(String a,String b){
        char[] aArr = a.toCharArray();
        char[] bArr = b.toCharArray();
        int max = Math.max(a.length(), b.length());
        String [] endArr = new String [max+2];
        Arrays.fill(endArr,null);
        Stack<Character> stacka = new Stack<>();
        Stack<Character> stackb = new Stack<>();
        // 321 放入 出来的顺序是 123， 1作为最末尾，
        // 65 放入 出来的顺序是 56   5作为最末尾
        for(int i=aArr.length-1;i>=0;i--){
            stacka.push(aArr[i]);
        }
        for(int i=bArr.length-1;i>=0;i--){
            stackb.push(bArr[i]);
        }
        int index = max-1;
        while(!stacka.isEmpty() || !stackb.isEmpty()){
            if(stacka.size() > stackb.size()){
                endArr[index]=stacka.pop()+"";
                index--;
            }else if(stackb.size() > stacka.size()){
                endArr[index]=stackb.pop()+"";
                index--;
            }else{
                //如果相等，考虑溢出情况
                Integer tempa = new Integer(stacka.pop()+"");
                Integer tempb = new Integer(stackb.pop()+"");
                diguiAdd(tempa,tempb,endArr,index);
                index--;
            }
        }
        StringBuffer end = new StringBuffer();
        for(int i=endArr.length-1;i>=0;i--){
            if(endArr[i] != null){
                end.append(endArr[i]);
            }
        }
        return end.toString();
    }
    //递归累加 往上递增
    public static void diguiAdd(int a,int b,String [] arr,int index){
        int end = a + b;
        if(end < 10){
            arr[index] = end+"";
            return;
        }else{
            int yushu = end % 10;
            end = end/10;
            arr[index]=yushu+"";
            index++;
            Integer tempb = 0;
            if(arr[index]!=null){
                tempb = Integer.parseInt(arr[index]);
            }
            diguiAdd(end,tempb ,arr, index);
        }
    }

    public static void main(String[] args) {
        String multipy = multipy("123", "456");
        System.out.println(multipy);
//        String aad= add("60","369");
//        System.out.println(aad);
    }


}
